\section{美团专题}
\begin{Textcode}
	现在有一个城市销售经理，需要从公司出发，去拜访市内的某位商家，已知他的位置以及商家的位置，但是由于城市道路交通的原因，他每次移动只能在左右中选择一个方向或在上下中选择一个方向，现在问他有多少种最短方案到达商家地址。给定一个地图 CityMap 及它的 行长度 n 和 列长度 m ，其中1代表经理位置， 2 代表商家位置， -1 代表不能经过的地区， 0 代表可以经过的地区，请返回方案数，保证一定存在合法路径。保证矩阵的长宽都小于等于 10。
\end{Textcode}
\begin{itemize}
	\item 注意：需保证所有方案的距离都是最短的方案
	\item 数据范围：
	      例如当输入为[[2,0,0,0],[0,-1,-1,0],[0,-1,1,0],[0,0,0,0]],4,4时，对应的4行4列CityMap如下\figref{fig:countPath}所示。
\end{itemize}

经理的位置在(2,2)，商家的位置在(0,0)，经分析，经理到达商家地址的最短方案有两种，分别为：
(2,2)->(2,3)->(1,3)->(0,3)->(0,2)->(0,1)->(0,0)
和
(2,2)->(3,2)->(3,1)->(3,0)->(2,0)->(1,0)->(0,0)，所以对应的返回值为2
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.5\textwidth]{figures/countPath}
	\end{center}
	\caption{到达商家的最短路径数}
	\label{fig:countPath}
\end{figure}
\begin{Mind}{拜访}
	先找到出发起点位置，从起点开始DFS，如果到达商家则将路径存储起来，最后找到所有到达商家的路径然后统计其中最小的次数。需要注意的是这里求路径和最小的次数，说明路径访问可以重复。如果设置 visited[r][c] = true ，只表示在这个路径中起被访问过，无法如果设置为true后不修改回来会导致走其他路径的时候收到影响。
\end{Mind}
实现如\coderef{code:visitClient}
\begin{listing}[!htbp]
	\caption{拜访客户}
	\cppfile[firstline=38,lastline=77]{third_party/coding/cxx/algorithm/common/src/mtBasic.cc}
	\label{code:visitClient}
\end{listing}
\subsection{bit位数}
两个整数 m 和 n 的二进制表达中有多少个位(bit)不同？输入15，8输出3。实现思路：m和n异或计算1的个数，实现\coderef{code:bitDiffNums}。
\begin{listing}[!htbp]
	\caption{两个数bit位不同的个数}
	\cppfile[firstline=11,lastline=17]{third_party/coding/cxx/algorithm/common/src/bitDiffNums.cc}
	\label{code:bitDiffNums}
\end{listing}
\subsection{丢弃奇数位后剩余数字}
输入数值为9，则序列为0，1，2，3，4，5，6，7，8，9。按照要求首先去除奇数位位0，2，4，6，8，剩余的数字为1，3，5，7，9，第二轮操作去除1，5，9，剩余3，7，最后一轮操作则是去除3，剩余的数字是7。最后剩余数字为1最多的数字。

\begin{listing}[!htbp]
	\caption{两个数bit位不同的个数}
	\cppfile[firstline=13,lastline=23]{third_party/coding/cxx/algorithm/common/src/bitDiffNums.cc}
	\label{code:bitDiffNums}
\end{listing}
\subsection{二维数组打印}
有一个二维数组 ($n\times n$) ,写程序实现从右上角到左下角沿主对角线方向打印。示意图如：
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.5\textwidth]{arrayPrint}
	\end{center}
	\caption{打印二维数组}
	\label{fig:arrayPrint}
\end{figure}
\begin{Mind}{二维数组打印}
	以左上角元素为起点BFS，每次将元素左边和下边的元素作为节点的子节点，如果节点已经存在则丢弃。
\end{Mind}
代码如\coderef{code:printArray}。
\begin{listing}[!htbp]
	\caption{二维数组打印}
	\cppfile[firstline=26,lastline=62]{third_party/coding/cxx/algorithm/common/src/bitDiffNums.cc}
	\label{code:printArray}
\end{listing}
\subsection{股票交易日}
在股市的交易日中，假设最多可进行两次买卖(即买和卖的次数均小于等于 2 )，规则是必须一笔成交后进行另一笔(即买-卖-买-卖的顺序进行)。给出一天中的股票变化序列，请写一个程序计算一天可以获得的最大收益。请采用时间复杂度低的方法实现。给定价格序列 prices 及它的长度 n ，请返回最大收益。
\begin{Mind}{股票交易日（两次）}{}
	这个题目类似于股票买卖获取最大收益，不同在于这里交易被限制了买卖只能有两笔。即只能买-卖完成两次。假设：
	\begin{itemize}
		\item dp[i][0]：第i天第一次买入的最大收益。
		\item dp[i][1]：第i天第一次卖出的最大收益。
		\item dp[i][2]：第i天第二次买入的最大收益。
		\item dp[i][3]：第i天第二次卖出的最大收益。
	\end{itemize}
	dp[i][3]表示第二次卖出的最大收益，对于前一天可能是第二次买入，即dp[i][2]，收益为dp[i][2]+prices[i]，也可能是第二次卖出（今天则无法卖出，因为两次交易已经完成，收益保持不变），收益为dp[i-1]，这里需要注意的是只能买卖、买卖这样操作不能买买、卖卖。
	最后收益最大一定是第二次卖出得到的收益最大，即dp[i][3]。
\end{Mind}
\begin{itemize}
	\item 状态：dp[i][j]表示第i天第一次、第二次、买、卖的收益。
	\item 转移条件：\begin{equation*}
		      \begin{split}
			      dp[i][0] &= max(dp[i-1][0],-prices[i])\\
			      dp[i][1] &= max(dp[i-1][0]+prices[i],dp[i-1][1])\\
			      dp[i][2] &= max(dp[i-1][1]-prices[i-1],dp[i-1][2])\\
			      dp[i][3] &= max(dp[i-1][0]+prices[i-1],dp[i-1][1])\\
		      \end{split}
	      \end{equation*}
	\item 边界条件：dp[0][0]=-prices[0]，dp[0][1]=0、dp[0][2]=-prices[0]、dp[0][3]=0。
\end{itemize}
\subsection{直方图内最大矩形}
给定一个数组heights，长度为n，height[i]是在第 i 点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少?
\begin{enumerate}
	\item 每个直方图宽度都为1。
	\item 直方图都是相邻的。
	\item 如果不能形成矩形，返回0即可。
	\item 保证返回的结果不会超过$2^{31}-1$。
\end{enumerate}
如输入[3,4,7,8,1,2]，输出14。
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.5\textwidth]{largestRectangleArea}
	\end{center}
	\caption{直方图内最大矩形}
	\label{fig:largestRectangleArea}
\end{figure}
矩形的面积为矩形条的宽度h和高度w的乘积，要想面积最大只需要h固定的时候w最大或者w固定的时候h最大。这里以h固定为例说明，如果heights[i]的高度知道了，想知道通过它能找到最大矩形。我们可以以其作为起点左右移动，往左边能移动说明了左边的高度必然不能小于当前高度，否则计算面积的时候高度变小了。往右边移动同理，所以以i为固定高度，能找到得最大面积是从i出发左右移动最后到第一个<heights[i]的位置为止。我们遍历整个高度然后求出每个高度下能达到的最大面积找出最大值即可。暴力解法实现如：

\begin{listing}[!htbp]
	\caption{直方图内最大矩形（暴力）}
	\cppfile[firstline=79,lastline=99]{third_party/coding/cxx/algorithm/common/src/mtBasic.cc}
	\label{code:largestRectangleAreaBrute}
\end{listing}

\begin{itemize}
	\item 时间复杂度O($n^2$)。
	\item 空间复杂度O(1)。
\end{itemize}
分析上述问题，我们左右搜索找到第一个严格大于当前元素的元素。最差情况下每次都需要遍历整个数组才能找到。如果我们能将严格大于当前的元素以特定的数据结构存储起来然后能以O(1)访问到对应的元素，算法时间复杂度将能降到O(n)。单调栈实现:

\begin{listing}[!htbp]
	\caption{直方图内最大矩形（单调栈（非减））}
	\cppfile[firstline=101,lastline=120]{third_party/coding/cxx/algorithm/common/src/mtBasic.cc}
	\label{code:largestRectangleAreaStack}
\end{listing}
对于heights = [2,1,5,6,2,3]
\begin{enumerate}
	\item 单调栈为空，2入栈（这里说的2入栈意味着索引1入栈）。
	\item 1比栈顶元素小，入栈，更新最大值为2（此时只有一个元素它的面积为heights[0]*1）。
	\item 5、6递增，入栈，根据1计算左右能到达的最大面积3。然后2出栈5入栈。
	\item 2小于栈顶元素6，更新最大值6，接着发现2小于5，接着更新最大值10，直到1<2，将2入栈。
	\item 3入栈。
\end{enumerate}
这里需要注意的是当发现i所在元素$\leq$栈顶索引对应的元素时计算面积是以当前i，开始从栈顶元素的左边开始计算，索引宽度为i-s.top()-1。给height添加0是为了防止全递增情况下(1,2,2)，没有找到小于栈中元素的情况，一旦有0，它一定不比栈顶元素大。故而可以参与到里面面积的运算。
\subsection{最大矩形}
给定一个仅包含 0 和 1 、大小为 $rows \times cols$ 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
\begin{Textcode}
	输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
	输出：6
\end{Textcode}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.95\textwidth]{maximalRectangle}
	\end{center}
	\caption{最大矩形}
	\label{fig:maximalRectangle}
\end{figure}
和直方图最大面积类似，对数据每一行进行更新求累计和之后按照直方图的最大矩形更新。需要强调的是有时候会出现悬空的情况，如\figref{fig:maximalRectangle}中紫色区域，从最后一行的角度看其是悬空的，但是没关系因为倒数第二行已经更新了它的面积最大的值。到最后一行的时候这一列置0。

\begin{listing}[!htbp]
	\caption{最大矩形面积}
	\cppfile[firstline=122,lastline=141]{third_party/coding/cxx/algorithm/common/src/mtBasic.cc}
	\label{code:maximalRectangle}
\end{listing}
